package com.fox.imagedb.ui;

/*
 * @(#)VariableHeightLayoutCache.java	1.22 05/11/17
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

import java.awt.Rectangle;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.NoSuchElementException;
import java.util.Stack;
import java.util.Vector;

import javax.swing.event.TreeModelEvent;
import javax.swing.tree.AbstractLayoutCache;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.MutableTreeNode;
import javax.swing.tree.TreeModel;
import javax.swing.tree.TreeNode;
import javax.swing.tree.TreePath;

/**
 * NOTE: This will become more open in a future release.
 * <p>
 * <strong>Warning:</strong> Serialized objects of this class will not be
 * compatible with future Swing releases. The current serialization support is
 * appropriate for short term storage or RMI between applications running the
 * same version of Swing. As of 1.4, support for long term storage of all
 * JavaBeans<sup><font size="-2">TM</font></sup> has been added to the
 * <code>java.beans</code> package. Please see {@link java.beans.XMLEncoder}.
 * 
 * @version 1.22 11/17/05
 * @author Rob Davis
 * @author Ray Ryan
 * @author Scott Violet
 */

public class PhylTreeLayoutCache extends AbstractLayoutCache {

	/**
	 * The array of nodes that are currently visible, in the order they are
	 * displayed.
	 */
	private Vector<PhylTreeStateNode> visibleNodes;

	/**
	 * This is set to true if one of the entries has an invalid size.
	 */
	private boolean updateNodeSizes;

	/**
	 * The root node of the internal cache of nodes that have been shown. If the
	 * treeModel is vending a network rather than a true tree, there may be one
	 * cached node for each path to a modeled node.
	 */
	private PhylTreeStateNode root;

	/**
	 * Used in getting sizes for nodes to avoid creating a new Rectangle every
	 * time a size is needed.
	 */
	private Rectangle boundsBuffer;

	/**
	 * Maps from <code>TreePath</code> to a <code>TreeStateNode</code>.
	 */
	private Hashtable<TreePath, PhylTreeStateNode> treePathMapping;

	/**
	 * A stack of stacks.
	 */
	private Stack<Stack<TreePath>> tempStacks;

	public PhylTreeLayoutCache() {
		super();
		tempStacks = new Stack<Stack<TreePath>>();
		visibleNodes = new Vector<PhylTreeStateNode>();
		boundsBuffer = new Rectangle();
		treePathMapping = new Hashtable<TreePath, PhylTreeStateNode>();
	}

	/**
	 * Sets the <code>TreeModel</code> that will provide the data.
	 * 
	 * @param newModel
	 *            the <code>TreeModel</code> that is to provide the data
	 * @beaninfo bound: true description: The TreeModel that will provide the
	 *           data.
	 */
	@Override
	public void setModel(TreeModel newModel) {
		super.setModel(newModel);
		rebuild(false);
	}

	/**
	 * Determines whether or not the root node from the <code>TreeModel</code>
	 * is visible.
	 * 
	 * @param rootVisible
	 *            true if the root node of the tree is to be displayed
	 * @see #rootVisible
	 * @beaninfo bound: true description: Whether or not the root node from the
	 *           TreeModel is visible.
	 */
	@Override
	public void setRootVisible(boolean rootVisible) {
		if ((isRootVisible() != rootVisible) && (root != null)) {
			if (rootVisible) {
				root.updatePreferredSize(0);
				visibleNodes.insertElementAt(root, 0);
			} else if (visibleNodes.size() > 0) {
				visibleNodes.removeElementAt(0);
				if (treeSelectionModel != null) {
					treeSelectionModel.removeSelectionPath(root.getTreePath());
				}
			}
			if (treeSelectionModel != null) {
				treeSelectionModel.resetRowSelection();
			}
			if (getRowCount() > 0) {
				getNode(0).setYOrigin(0);
			}
			updateYLocationsFrom(0);
			visibleNodesChanged();
		}
		super.setRootVisible(rootVisible);
	}

	/**
	 * Sets the height of each cell. If the specified value is less than or
	 * equal to zero the current cell renderer is queried for each row's height.
	 * 
	 * @param rowHeight
	 *            the height of each cell, in pixels
	 * @beaninfo bound: true description: The height of each cell.
	 */
	@Override
	public void setRowHeight(int rowHeight) {
		if (rowHeight != getRowHeight()) {
			super.setRowHeight(rowHeight);
			invalidateSizes();
			this.visibleNodesChanged();
		}
	}

	/**
	 * Sets the renderer that is responsible for drawing nodes in the tree.
	 * 
	 * @param nd
	 *            the renderer
	 */
	@Override
	public void setNodeDimensions(NodeDimensions nd) {
		super.setNodeDimensions(nd);
		invalidateSizes();
		visibleNodesChanged();
	}

	/**
	 * Marks the path <code>path</code> expanded state to
	 * <code>isExpanded</code>.
	 * 
	 * @param path
	 *            the <code>TreePath</code> of interest
	 * @param isExpanded
	 *            true if the path should be expanded, otherwise false
	 */
	@Override
	public void setExpandedState(TreePath path, boolean isExpanded) {
		if (path != null) {
			if (isExpanded) {
				ensurePathIsExpanded(path, true);
			} else {
				PhylTreeStateNode node = getNodeForPath(path, true);

				if (node != null) {
					node.makeVisible();
				}
			}
		}
	}

	/**
	 * Returns true if the path is expanded, and visible.
	 * 
	 * @return true if the path is expanded and visible, otherwise false
	 */
	@Override
	public boolean getExpandedState(TreePath path) {
		PhylTreeStateNode node = getNodeForPath(path, false);

		return (node != null) ? true : false;
	}

	/**
	 * Returns the <code>Rectangle</code> enclosing the label portion into which
	 * the item identified by <code>path</code> will be drawn.
	 * 
	 * @param path
	 *            the path to be drawn
	 * @param placeIn
	 *            the bounds of the enclosing rectangle
	 * @return the bounds of the enclosing rectangle or <code>null</code> if the
	 *         node could not be ascertained
	 */
	@Override
	public Rectangle getBounds(TreePath path, Rectangle placeIn) {
		PhylTreeStateNode node = getNodeForPath(path, false);

		if (node != null) {
			if (updateNodeSizes) {
				updateNodeSizes(false);
			}
			return node.getNodeBounds(placeIn);
		}
		return null;
	}

	public int getPathLineIndent(TreePath path) {
		PhylTreeStateNode node = getNodeForPath(path, false);
		if (node != null && node.getParent() != null) {
			return ((PhylTreeStateNode) node).getXIndent();
		}
		return 0;
	}

	/**
	 * Returns the path for <code>row</code>. If <code>row</code> is not
	 * visible, <code>null</code> is returned.
	 * 
	 * @param row
	 *            the location of interest
	 * @return the path for <code>row</code>, or <code>null</code> if
	 *         <code>row</code> is not visible
	 */
	@Override
	public TreePath getPathForRow(int row) {
		if ((row >= 0) && (row < getRowCount())) {
			return getNode(row).getTreePath();
		}
		return null;
	}

	/**
	 * Returns the row where the last item identified in path is visible. Will
	 * return -1 if any of the elements in path are not currently visible.
	 * 
	 * @param path
	 *            the <code>TreePath</code> of interest
	 * @return the row where the last item in path is visible
	 */
	@Override
	public int getRowForPath(TreePath path) {
		if (path == null) {
			return -1;
		}

		PhylTreeStateNode visNode = getNodeForPath(path, false);

		if (visNode != null) {
			return visNode.getRow();
		}
		return -1;
	}

	/**
	 * Returns the number of visible rows.
	 * 
	 * @return the number of visible rows
	 */
	@Override
	public int getRowCount() {
		return visibleNodes.size();
	}

	/**
	 * Instructs the <code>LayoutCache</code> that the bounds for
	 * <code>path</code> are invalid, and need to be updated.
	 * 
	 * @param path
	 *            the <code>TreePath</code> which is now invalid
	 */
	@Override
	public void invalidatePathBounds(TreePath path) {
		PhylTreeStateNode node = getNodeForPath(path, false);

		if (node != null) {
			node.markSizeInvalid();
			updateYLocationsFrom(node.getRow());
		}
	}

	/**
	 * Returns the preferred height.
	 * 
	 * @return the preferred height
	 */
	@Override
	public int getPreferredHeight() {
		// Get the height
		int rowCount = getRowCount();

		if (rowCount > 0) {
			PhylTreeStateNode node = getNode(rowCount - 1);

			return node.getYOrigin() + node.getPreferredHeight();
		}
		return 0;
	}

	/**
	 * Returns the preferred width and height for the region in
	 * <code>visibleRegion</code>.
	 * 
	 * @param bounds
	 *            the region being queried
	 */
	@Override
	public int getPreferredWidth(Rectangle bounds) {
		if (updateNodeSizes) {
			updateNodeSizes(false);
		}

		return getMaxNodeWidth();
	}

	/**
	 * Returns the path to the node that is closest to x,y. If there is nothing
	 * currently visible this will return <code>null</code>, otherwise it will
	 * always return a valid path. If you need to test if the returned object is
	 * exactly at x, y you should get the bounds for the returned path and test
	 * x, y against that.
	 * 
	 * @param x
	 *            the x-coordinate
	 * @param y
	 *            the y-coordinate
	 * @return the path to the node that is closest to x, y
	 */
	@Override
	public TreePath getPathClosestTo(int x, int y) {
		if (getRowCount() == 0) {
			return null;
		}

		if (updateNodeSizes) {
			updateNodeSizes(false);
		}

		int row = getRowContainingLocation(x, y);

		if (x > 0) {
			return getNode(row).getTreePath();
		}

		// Si x = 0, on est dans le repaint de la ligne selectionnee. On renvoie
		// le premier parent de la ligne
		return getFirstAlignedParent(getNode(row)).getTreePath();
	}

	private PhylTreeStateNode getFirstAlignedParent(TreeNode node) {
		if (node != null && node.getParent() != null
				&& node.getParent().getIndex(node) == 0) {
			return getFirstAlignedParent(node.getParent());
		}
		return (PhylTreeStateNode) node;
	}

	/**
	 * Returns an <code>Enumerator</code> that increments over the visible paths
	 * starting at the passed in location. The ordering of the enumeration is
	 * based on how the paths are displayed.
	 * 
	 * @param path
	 *            the location in the <code>TreePath</code> to start
	 * @return an <code>Enumerator</code> that increments over the visible paths
	 */
	@Override
	public Enumeration<TreePath> getVisiblePathsFrom(TreePath path) {
		PhylTreeStateNode node = getNodeForPath(path, false);

		if (node != null) {
			return new PhylTreeStateNodeEnumeration(node);
		}
		return null;
	}

	/**
	 * Returns the number of visible children for <code>path</code>.
	 * 
	 * @return the number of visible children for <code>path</code>
	 */
	@Override
	public int getVisibleChildCount(TreePath path) {
		PhylTreeStateNode node = getNodeForPath(path, false);

		return (node != null) ? node.getVisibleChildCount() : 0;
	}

	/**
	 * Informs the <code>TreeState</code> that it needs to recalculate all the
	 * sizes it is referencing.
	 */
	@Override
	public void invalidateSizes() {
		if (root != null) {
			root.deepMarkSizeInvalid();
		}
		if (!isFixedRowHeight() && (visibleNodes.size() > 0)) {
			updateNodeSizes(true);
		}
	}

	/**
	 * Returns true if the value identified by <code>path</code> is currently
	 * expanded.
	 * 
	 * @return true if the value identified by <code>path</code> is currently
	 *         expanded
	 */
	@Override
	public boolean isExpanded(TreePath path) {
		if (path != null) {
			PhylTreeStateNode lastNode = getNodeForPath(path, false);

			return (lastNode != null);
		}
		return false;
	}

	//
	// TreeModelListener methods
	//

	/**
	 * Invoked after a node (or a set of siblings) has changed in some way. The
	 * node(s) have not changed locations in the tree or altered their children
	 * arrays, but other attributes have changed and may affect presentation.
	 * Example: the name of a file has changed, but it is in the same location
	 * in the file system.
	 * 
	 * <p>
	 * <code>e.path</code> returns the path the parent of the changed node(s).
	 * 
	 * <p>
	 * <code>e.childIndices</code> returns the index(es) of the changed node(s).
	 * 
	 * @param e
	 *            the <code>TreeModelEvent</code> of interest
	 */
	@Override
	public void treeNodesChanged(TreeModelEvent e) {
		if (e != null) {
			int changedIndexs[];
			PhylTreeStateNode changedNode;

			changedIndexs = e.getChildIndices();
			changedNode = getNodeForPath(e.getTreePath(), false);
			if (changedNode != null) {
				Object changedValue = changedNode.getValue();

				/*
				 * Update the size of the changed node, as well as all the child
				 * indexs that are passed in.
				 */
				changedNode.updatePreferredSize();
				if (changedNode.hasBeenExpanded() && (changedIndexs != null)) {
					int counter;
					PhylTreeStateNode changedChildNode;

					for (counter = 0; counter < changedIndexs.length; counter++) {
						changedChildNode = (PhylTreeStateNode) changedNode
								.getChildAt(changedIndexs[counter]);
						/* Reset the user object. */
						changedChildNode.setUserObject(treeModel.getChild(
								changedValue, changedIndexs[counter]));
						changedChildNode.updatePreferredSize();
					}
				} else if (changedNode == root) {
					// Null indicies for root indicates it changed.
					changedNode.updatePreferredSize();
				}
				if (!isFixedRowHeight()) {
					int aRow = changedNode.getRow();

					if (aRow != -1) {
						this.updateYLocationsFrom(aRow);
					}
				}
				this.visibleNodesChanged();
			}
		}
	}

	/**
	 * Invoked after nodes have been inserted into the tree.
	 * 
	 * <p>
	 * <code>e.path</code> returns the parent of the new nodes.
	 * <p>
	 * <code>e.childIndices</code> returns the indices of the new nodes in
	 * ascending order.
	 * 
	 * @param e
	 *            the <code>TreeModelEvent</code> of interest
	 */
	@Override
	public void treeNodesInserted(TreeModelEvent e) {
		if (e != null) {
			int changedIndexs[];
			PhylTreeStateNode changedParentNode;

			changedIndexs = e.getChildIndices();
			changedParentNode = getNodeForPath(e.getTreePath(), false);

			/*
			 * Only need to update the children if the node has been expanded
			 * once.
			 */
			// PENDING(scott): make sure childIndexs is sorted!
			if ((changedParentNode != null) && (changedIndexs != null)
					&& (changedIndexs.length > 0)) {
				int counter;
				int oldChildCount = changedParentNode.getChildCount();

				for (counter = 0; counter < changedIndexs.length; counter++) {
					this.createNodeAt(changedParentNode, changedIndexs[counter]);
				}
				if (oldChildCount == 0) {
					// Update the size of the parent.
					changedParentNode.updatePreferredSize();
				}
				if (treeSelectionModel != null) {
					treeSelectionModel.resetRowSelection();
				}
				/*
				 * Update the y origins from the index of the parent to the end
				 * of the visible rows.
				 */
				if (!isFixedRowHeight()) {
					if (changedParentNode == root) {
						this.updateYLocationsFrom(0);
					} else {
						this.updateYLocationsFrom(changedParentNode.getRow());
					}
				}
				this.visibleNodesChanged();
			}
		}
	}

	/**
	 * Invoked after nodes have been removed from the tree. Note that if a
	 * subtree is removed from the tree, this method may only be invoked once
	 * for the root of the removed subtree, not once for each individual set of
	 * siblings removed.
	 * 
	 * <p>
	 * <code>e.path</code> returns the former parent of the deleted nodes.
	 * 
	 * <p>
	 * <code>e.childIndices</code> returns the indices the nodes had before they
	 * were deleted in ascending order.
	 * 
	 * @param e
	 *            the <code>TreeModelEvent</code> of interest
	 */
	@Override
	public void treeNodesRemoved(TreeModelEvent e) {
		if (e != null) {
			int changedIndexs[];
			PhylTreeStateNode changedParentNode;

			changedIndexs = e.getChildIndices();
			changedParentNode = getNodeForPath(e.getTreePath(), false);
			// PENDING(scott): make sure that changedIndexs are sorted in
			// ascending order.
			if ((changedParentNode != null) && (changedIndexs != null)
					&& (changedIndexs.length > 0)) {
				if (changedParentNode.hasBeenExpanded()) {
					boolean makeInvisible;
					int counter;
					int removedRow;
					PhylTreeStateNode removedNode;

					makeInvisible = (((changedParentNode == root) && !rootVisible) || (changedParentNode
							.getRow() != -1));
					for (counter = changedIndexs.length - 1; counter >= 0; counter--) {
						removedNode = (PhylTreeStateNode) changedParentNode
								.getChildAt(changedIndexs[counter]);

						/* Let the selection model now. */
						if (makeInvisible) {
							removedRow = removedNode.getRow();
							if (removedRow != -1) {
								visibleNodes.removeElementAt(removedRow);
							}
						}
						changedParentNode.remove(changedIndexs[counter]);
					}
					if (changedParentNode.getChildCount() == 0) {
						// Update the size of the parent.
						changedParentNode.updatePreferredSize();
					}
					if (treeSelectionModel != null) {
						treeSelectionModel.resetRowSelection();
					}
					/*
					 * Update the y origins from the index of the parent to the
					 * end of the visible rows.
					 */
					if (!isFixedRowHeight()
							&& (makeInvisible || (changedParentNode
									.getChildCount() == 0))) {
						if (changedParentNode == root) {
							/*
							 * It is possible for first row to have been removed
							 * if the root isn't visible, in which case
							 * ylocations will be off!
							 */
							if (getRowCount() > 0) {
								getNode(0).setYOrigin(0);
							}
							updateYLocationsFrom(0);
						} else {
							updateYLocationsFrom(changedParentNode.getRow());
						}
						this.visibleNodesChanged();
					} else if (makeInvisible) {
						this.visibleNodesChanged();
					}
				} else if (treeModel
						.getChildCount(changedParentNode.getValue()) == 0) {
					changedParentNode.updatePreferredSize();
					if (!isFixedRowHeight()) {
						this.updateYLocationsFrom(changedParentNode.getRow());
					}
				}
			}
		}
	}

	/**
	 * Invoked after the tree has drastically changed structure from a given
	 * node down. If the path returned by <code>e.getPath</code> is of length
	 * one and the first element does not identify the current root node the
	 * first element should become the new root of the tree.
	 * 
	 * <p>
	 * <code>e.path</code> holds the path to the node.
	 * <p>
	 * <code>e.childIndices</code> returns <code>null</code>.
	 * 
	 * @param e
	 *            the <code>TreeModelEvent</code> of interest
	 */
	@Override
	public void treeStructureChanged(TreeModelEvent e) {
		if (e != null) {
			TreePath changedPath = e.getTreePath();
			PhylTreeStateNode changedNode;

			changedNode = getNodeForPath(changedPath, false);

			// Check if root has changed, either to a null root, or
			// to an entirely new root.
			if ((changedNode == root)
					|| ((changedNode == null) && (((changedPath == null)
							&& (treeModel != null) && (treeModel.getRoot() == null)) || ((changedPath != null) && (changedPath
							.getPathCount() == 1))))) {
				rebuild(true);
			} else if (changedNode != null) {
				int nodeIndex;
				PhylTreeStateNode newNode, parent;
				boolean wasExpanded, wasVisible;
				int newIndex;

				wasExpanded = true;
				wasVisible = (changedNode.getRow() != -1);
				/* Remove the current node and recreate a new one. */
				parent = (PhylTreeStateNode) changedNode.getParent();
				nodeIndex = parent.getIndex(changedNode);
				if (wasVisible) {
					visibleNodes.removeElement(changedNode);
				}
				changedNode.removeFromParent();
				createNodeAt(parent, nodeIndex);
				newNode = (PhylTreeStateNode) parent.getChildAt(nodeIndex);
				if (wasVisible && wasExpanded) {
					newNode.expand();
				}
				newIndex = newNode.getRow();
				if (!isFixedRowHeight() && wasVisible) {
					if (newIndex == 0) {
						updateYLocationsFrom(newIndex);
					} else {
						updateYLocationsFrom(newIndex - 1);
					}
					this.visibleNodesChanged();
				} else if (wasVisible) {
					this.visibleNodesChanged();
				}
			}
		}
	}

	//
	// Local methods
	//

	private void visibleNodesChanged() {
	}

	/**
	 * Adds a mapping for node.
	 */
	private void addMapping(PhylTreeStateNode node) {
		treePathMapping.put(node.getTreePath(), node);
	}

	/**
	 * Removes the mapping for a previously added node.
	 */
	private void removeMapping(PhylTreeStateNode node) {
		treePathMapping.remove(node.getTreePath());
	}

	/**
	 * Returns the node previously added for <code>path</code>. This may return
	 * null, if you to create a node use getNodeForPath.
	 */
	private PhylTreeStateNode getMapping(TreePath path) {
		return treePathMapping.get(path);
	}

	/**
	 * Completely rebuild the tree, all expanded state, and node caches are
	 * removed. All nodes are collapsed, except the root.
	 */
	private void rebuild(boolean clearSelection) {
		Object rootObject;

		treePathMapping.clear();
		if ((treeModel != null) && ((rootObject = treeModel.getRoot()) != null)) {
			root = createNodeForValue(rootObject);
			// FIXME
			root.setYOrigin(50);
			root.path = new TreePath(rootObject);
			addMapping(root);
			root.updatePreferredSize(0);
			visibleNodes.removeAllElements();
			if (isRootVisible()) {
				visibleNodes.addElement(root);
			}
			if (!root.hasBeenExpanded()) {
				root.expandAll();

				if (!isFixedRowHeight()) {
					updateYLocationsFrom(0);
				}
			}

		} else {
			visibleNodes.removeAllElements();
			root = null;
		}
		if (clearSelection && (treeSelectionModel != null)) {
			treeSelectionModel.clearSelection();
		}
		this.visibleNodesChanged();
	}

	/**
	 * Creates a new node to represent the node at <I>childIndex</I> in
	 * <I>parent</I>s children. This should be called if the node doesn't
	 * already exist and <I>parent</I> has been expanded at least once. The
	 * newly created node will be made visible if <I>parent</I> is currently
	 * expanded. This does not update the position of any cells, nor update the
	 * selection if it needs to be. If succesful in creating the new
	 * TreeStateNode, it is returned, otherwise null is returned.
	 */
	private PhylTreeStateNode createNodeAt(PhylTreeStateNode parent,
			int childIndex) {
		boolean isParentRoot;
		Object newValue;
		PhylTreeStateNode newChildNode;

		newValue = treeModel.getChild(parent.getValue(), childIndex);
		newChildNode = createNodeForValue(newValue);
		parent.insert(newChildNode, childIndex);
		newChildNode.updatePreferredSize(-1);
		isParentRoot = (parent == root);
		if ((newChildNode != null) && ((parent.getRow() != -1) || isParentRoot)) {
			int newRow;

			/* Find the new row to insert this newly visible node at. */
			if (childIndex == 0) {
				if (isParentRoot && !isRootVisible()) {
					newRow = 0;
				} else {
					newRow = parent.getRow() + 1;
				}
			} else if (childIndex == parent.getChildCount()) {
				newRow = parent.getLastVisibleNode().getRow() + 1;
			} else {
				PhylTreeStateNode previousNode;

				previousNode = (PhylTreeStateNode) parent
						.getChildAt(childIndex - 1);
				newRow = previousNode.getLastVisibleNode().getRow() + 1;
			}
			visibleNodes.insertElementAt(newChildNode, newRow);
		}
		return newChildNode;
	}

	/**
	 * Returns the TreeStateNode identified by path. This mirrors the behavior
	 * of getNodeForPath, but tries to take advantage of path if it is an
	 * instance of AbstractTreePath.
	 */
	private PhylTreeStateNode getNodeForPath(TreePath path, boolean shouldCreate) {
		if (path != null) {
			PhylTreeStateNode node;

			node = getMapping(path);
			if (node != null) {
				return node;
			}

			// Check all the parent paths, until a match is found.
			Stack<TreePath> paths;

			if (tempStacks.size() == 0) {
				paths = new Stack<TreePath>();
			} else {
				paths = tempStacks.pop();
			}

			try {
				paths.push(path);
				path = path.getParentPath();
				node = null;
				while (path != null) {
					node = getMapping(path);
					if (node != null) {
						// Found a match, create entries for all paths in
						// paths.
						while ((node != null) && (paths.size() > 0)) {
							path = paths.pop();
							node.getLoadedChildren(shouldCreate);

							int childIndex = treeModel.getIndexOfChild(
									node.getUserObject(),
									path.getLastPathComponent());

							if ((childIndex == -1)
									|| (childIndex >= node.getChildCount())) {
								node = null;
							} else {
								node = (PhylTreeStateNode) node
										.getChildAt(childIndex);
							}
						}
						return node;
					}
					paths.push(path);
					path = path.getParentPath();
				}
			} finally {
				paths.removeAllElements();
				tempStacks.push(paths);
			}
			// If we get here it means they share a different root!
			// We could throw an exception...
		}
		return null;
	}

	/**
	 * Updates the y locations of all of the visible nodes after location.
	 */
	private void updateYLocationsFrom(int location) {
		int counter, maxCounter, newYOrigin;
		PhylTreeStateNode currentNode = getNode(location);

		PhylTreeStateNode previousNode = currentNode;
		newYOrigin = currentNode.getYOrigin();
		for (counter = location + 1, maxCounter = visibleNodes.size(); counter < maxCounter; counter++) {
			currentNode = visibleNodes.elementAt(counter);

			if (previousNode.getIndex(currentNode) != 0) {
				newYOrigin += currentNode.getPreferredHeight() + 10;
			}
			currentNode.setYOrigin(newYOrigin);
			previousNode = currentNode;
		}
	}

	/**
	 * Resets the y origin of all the visible nodes as well as messaging all the
	 * visible nodes to updatePreferredSize(). You should not normally have to
	 * call this. Expanding and contracting the nodes automaticly adjusts the
	 * locations. updateAll determines if updatePreferredSize() is call on all
	 * nodes or just those that don't have a valid size.
	 */
	private void updateNodeSizes(boolean updateAll) {
		// int aY, counter, maxCounter;
		// PhylTreeStateNode node;
		//
		// updateNodeSizes = false;
		// for (aY = counter = 0, maxCounter = visibleNodes.size(); counter <
		// maxCounter; counter++) {
		// node = visibleNodes.elementAt(counter);
		// node.setYOrigin(aY);
		// if (updateAll || !node.hasValidSize()) {
		// node.updatePreferredSize(counter);
		// }
		// aY += node.getPreferredHeight();
		// }
		updateNodeSizes = false;
		updateYLocationsFrom(0);
	}

	/**
	 * Returns the index of the row containing location. If there are no rows,
	 * -1 is returned. If location is beyond the last row index, the last row
	 * index is returned.
	 */
	private int getRowContainingLocation(int xLocation, int yLocation) {

		int max, maxY, mid, min, minY;
		PhylTreeStateNode node;

		if ((max = getRowCount()) <= 0) {
			return -1;
		}
		mid = min = 0;
		while (min < max) {
			mid = (max - min) / 2 + min;
			node = visibleNodes.elementAt(mid);
			minY = node.getYOrigin();
			maxY = minY + node.getPreferredHeight();
			if (yLocation < minY) {
				max = mid - 1;
			} else if (yLocation >= maxY) {
				min = mid + 1;
			} else {
				if (xLocation > 0) {
					if (xLocation >= node.getXOrigin() + node.preferredWidth) {
						min = mid + 1;
					} else if (xLocation < node.getXOrigin()) {
						max = mid - 1;
					} else {
						break;
					}
				} else {
					break;
				}

			}
		}
		if (min == max) {
			mid = min;
			if (mid >= getRowCount()) {
				mid = getRowCount() - 1;
			}
		}
		return mid;
	}

	/**
	 * Ensures that all the path components in path are expanded, accept for the
	 * last component which will only be expanded if expandLast is true. Returns
	 * true if succesful in finding the path.
	 */
	private void ensurePathIsExpanded(TreePath aPath, boolean expandLast) {
		if (aPath != null) {
			// Make sure the last entry isn't a leaf.
			if (treeModel.isLeaf(aPath.getLastPathComponent())) {
				aPath = aPath.getParentPath();
				expandLast = true;
			}
			if (aPath != null) {
				PhylTreeStateNode lastNode = getNodeForPath(aPath, true);

				if (lastNode != null) {
					lastNode.makeVisible();
					if (expandLast) {
						lastNode.expand();
					}
				}
			}
		}
	}

	/**
	 * Returns the AbstractTreeUI.VisibleNode displayed at the given row
	 */
	private PhylTreeStateNode getNode(int row) {
		return visibleNodes.elementAt(row);
	}

	/**
	 * Returns the maximum node width.
	 */
	private int getMaxNodeWidth() {
		int maxWidth = 0;
		int nodeWidth;
		int counter;
		PhylTreeStateNode node;

		for (counter = getRowCount() - 1; counter >= 0; counter--) {
			node = this.getNode(counter);
			nodeWidth = node.getPreferredWidth() + node.getXOrigin();
			if (nodeWidth > maxWidth) {
				maxWidth = nodeWidth;
			}
		}
		return maxWidth;
	}

	/**
	 * Responsible for creating a TreeStateNode that will be used to track
	 * display information about value.
	 */
	private PhylTreeStateNode createNodeForValue(Object value) {
		return new PhylTreeStateNode(value);
	}

	/**
	 * TreeStateNode is used to keep track of each of the nodes that have been
	 * expanded. This will also cache the preferred size of the value it
	 * represents.
	 */
	private class PhylTreeStateNode extends DefaultMutableTreeNode {

		private static final long serialVersionUID = -3504844922678376535L;

		/** Preferred size needed to draw the user object. */
		protected int preferredWidth;

		protected int preferredHeight;

		/** X location that the user object will be drawn at. */
		protected int xOrigin;

		/** Y location that the user object will be drawn at. */
		protected int yOrigin;

		protected int xIndent;

		/** Has this node been expanded at least once? */
		protected boolean hasBeenExpanded;

		/** Path of this node. */
		protected TreePath path;

		public PhylTreeStateNode(Object value) {
			super(value);
		}

		public void expandAll() {
			expand();
			Enumeration<PhylTreeStateNode> cursor = children();
			while (cursor.hasMoreElements()) {
				PhylTreeStateNode childNode = cursor.nextElement();
				childNode.expandAll();
			}

		}

		//
		// Overriden DefaultMutableTreeNode methods
		//

		/**
		 * Messaged when this node is added somewhere, resets the path and adds
		 * a mapping from path to this node.
		 */
		@Override
		public void setParent(MutableTreeNode parent) {
			super.setParent(parent);
			if (parent != null) {
				path = ((PhylTreeStateNode) parent).getTreePath()
						.pathByAddingChild(getUserObject());
				addMapping(this);
			}
		}

		/**
		 * Messaged when this node is removed from its parent, this messages
		 * <code>removedFromMapping</code> to remove all the children.
		 */
		@Override
		public void remove(int childIndex) {
			PhylTreeStateNode node = (PhylTreeStateNode) getChildAt(childIndex);

			node.removeFromMapping();
			super.remove(childIndex);
		}

		/**
		 * Messaged to set the user object. This resets the path.
		 */
		@Override
		public void setUserObject(Object o) {
			super.setUserObject(o);
			if (path != null) {
				PhylTreeStateNode parent = (PhylTreeStateNode) getParent();

				if (parent != null) {
					resetChildrenPaths(parent.getTreePath());
				} else {
					resetChildrenPaths(null);
				}
			}
		}

		/**
		 * Returns the children of the receiver. If the receiver is not
		 * currently expanded, this will return an empty enumeration.
		 */

		@Override
		@SuppressWarnings("unchecked")
		public Enumeration<PhylTreeStateNode> children() {
			return super.children();
		}

		/**
		 * Returns true if the receiver is a leaf.
		 */
		@Override
		public boolean isLeaf() {
			return getModel().isLeaf(this.getValue());
		}

		//
		// VariableHeightLayoutCache
		//

		/**
		 * Returns the location and size of this node.
		 */
		public Rectangle getNodeBounds(Rectangle placeIn) {
			if (placeIn == null) {
				placeIn = new Rectangle(getXOrigin(), getYOrigin(),
						getPreferredWidth(), getPreferredHeight());
			} else {
				placeIn.x = getXOrigin();
				placeIn.y = getYOrigin();
				placeIn.width = getPreferredWidth();
				placeIn.height = getPreferredHeight();
			}
			return placeIn;
		}

		public int getXIndent() {
			return xIndent;
		}

		/**
		 * @return x location to draw node at.
		 */
		public int getXOrigin() {
			if (!hasValidSize()) {
				updatePreferredSize(getRow());
			}
			return xOrigin;
		}

		/**
		 * Returns the y origin the user object will be drawn at.
		 */
		public int getYOrigin() {
			if (isFixedRowHeight()) {
				int aRow = getRow();

				if (aRow == -1) {
					return -1;
				}
				return getRowHeight() * aRow;
			}
			return yOrigin;
		}

		/**
		 * Returns the preferred height of the receiver.
		 */
		public int getPreferredHeight() {
			if (isFixedRowHeight()) {
				return getRowHeight();
			} else if (!hasValidSize()) {
				updatePreferredSize(getRow());
			}
			return preferredHeight;
		}

		/**
		 * Returns the preferred width of the receiver.
		 */
		public int getPreferredWidth() {
			if (!hasValidSize()) {
				updatePreferredSize(getRow());
			}
			return preferredWidth;
		}

		/**
		 * Returns true if this node has a valid size.
		 */
		public boolean hasValidSize() {
			return (preferredHeight != 0);
		}

		/**
		 * Returns the row of the receiver.
		 */
		public int getRow() {
			return visibleNodes.indexOf(this);
		}

		/**
		 * Returns true if this node has been expanded at least once.
		 */
		public boolean hasBeenExpanded() {
			return hasBeenExpanded;
		}

		/**
		 * Returns the last visible node that is a child of this instance.
		 */
		public PhylTreeStateNode getLastVisibleNode() {
			PhylTreeStateNode node = this;

			while (node.getChildCount() > 0) {
				node = (PhylTreeStateNode) node.getLastChild();
			}
			return node;
		}

		/**
		 * Returns the number of children this will have. If the children have
		 * not yet been loaded, this messages the model.
		 */
		public int getModelChildCount() {
			if (hasBeenExpanded) {
				return super.getChildCount();
			}
			return getModel().getChildCount(getValue());
		}

		/**
		 * Returns the number of visible children, that is the number of
		 * children that are expanded, or leafs.
		 */
		public int getVisibleChildCount() {
			int childCount = 0;

			int maxCounter = getChildCount();

			childCount += maxCounter;
			for (int counter = 0; counter < maxCounter; counter++) {
				childCount += ((PhylTreeStateNode) getChildAt(counter))
						.getVisibleChildCount();
			}
			return childCount;
		}

		/**
		 * Makes the receiver visible, but invoking
		 * <code>expandParentAndReceiver</code> on the superclass.
		 */
		public void makeVisible() {
			PhylTreeStateNode parent = (PhylTreeStateNode) getParent();

			if (parent != null) {
				parent.expandParentAndReceiver();
			}
		}

		/**
		 * Returns the value the receiver is representing. This is a cover for
		 * getUserObject.
		 */
		public Object getValue() {
			return getUserObject();
		}

		/**
		 * Returns a TreePath instance for this node.
		 */
		public TreePath getTreePath() {
			return path;
		}

		//
		// Local methods
		//

		/**
		 * Recreates the receivers path, and all its childrens paths.
		 */
		protected void resetChildrenPaths(TreePath parentPath) {
			removeMapping(this);
			if (parentPath == null) {
				path = new TreePath(getUserObject());
			} else {
				path = parentPath.pathByAddingChild(getUserObject());
			}
			addMapping(this);
			for (int counter = getChildCount() - 1; counter >= 0; counter--) {
				((PhylTreeStateNode) getChildAt(counter))
						.resetChildrenPaths(path);
			}
		}

		protected void setXIndent(int indent) {
			xIndent = indent;
		}

		/**
		 * Sets y origin the user object will be drawn at to <I>newYOrigin</I>.
		 */
		protected void setYOrigin(int newYOrigin) {
			yOrigin = newYOrigin;
		}

		/**
		 * Shifts the y origin by <code>offset</code>.
		 */
		protected void shiftYOriginBy(int offset) {
			yOrigin += offset;
		}

		/**
		 * Updates the receivers preferredSize by invoking
		 * <code>updatePreferredSize</code> with an argument of -1.
		 */
		protected void updatePreferredSize() {
			updatePreferredSize(getRow());
		}

		/**
		 * Updates the preferred size by asking the current renderer for the
		 * Dimension needed to draw the user object this instance represents.
		 */
		protected void updatePreferredSize(int index) {
			Rectangle bounds = getNodeDimensions(this.getUserObject(), index,
					getLevel(), true, boundsBuffer);

			if (bounds == null) {
				xOrigin = 0;
				preferredWidth = preferredHeight = 0;
				updateNodeSizes = true;
			} else {

				preferredWidth = (bounds.width == 0 ? 10 : bounds.width);

				if (bounds.height == 0) {
					// FIXME
					preferredHeight = 16;
					updateNodeSizes = true;
				} else {
					preferredHeight = bounds.height;
				}

				if (getParent() != null) {
					PhylTreeStateNode parentNode = (PhylTreeStateNode) getParent();
					xIndent = parentNode.getXOrigin()
							+ parentNode.getPreferredWidth();
					xOrigin = xIndent + 20;
				} else {
					xOrigin = 0;
					xIndent = 0;
				}
			}

		}

		/**
		 * Marks the receivers size as invalid. Next time the size, location is
		 * asked for it will be obtained.
		 */
		protected void markSizeInvalid() {
			preferredHeight = 0;
		}

		/**
		 * Marks the receivers size, and all its descendants sizes, as invalid.
		 */
		protected void deepMarkSizeInvalid() {
			markSizeInvalid();
			for (int counter = getChildCount() - 1; counter >= 0; counter--) {
				((PhylTreeStateNode) getChildAt(counter)).deepMarkSizeInvalid();
			}
		}

		/**
		 * Returns the children of the receiver. If the children haven't been
		 * loaded from the model and <code>createIfNeeded</code> is true, the
		 * children are first loaded.
		 */
		@SuppressWarnings("unchecked")
		protected Enumeration<PhylTreeStateNode> getLoadedChildren(
				boolean createIfNeeded) {
			if (!createIfNeeded || hasBeenExpanded) {
				return super.children();
			}

			PhylTreeStateNode newNode;
			Object realNode = getValue();
			TreeModel treeModel = getModel();
			int count = treeModel.getChildCount(realNode);

			hasBeenExpanded = true;

			int childRow = getRow();

			if (childRow == -1) {
				for (int i = 0; i < count; i++) {
					newNode = createNodeForValue(treeModel
							.getChild(realNode, i));
					this.add(newNode);
					newNode.updatePreferredSize(-1);
				}
			} else {
				childRow++;
				for (int i = 0; i < count; i++) {
					newNode = createNodeForValue(treeModel
							.getChild(realNode, i));
					this.add(newNode);
					newNode.updatePreferredSize(childRow++);
				}
			}
			return super.children();
		}

		/**
		 * Messaged from expand and collapse. This is meant for subclassers that
		 * may wish to do something interesting with this.
		 */
		protected void didAdjustTree() {
		}

		/**
		 * Invokes <code>expandParentAndReceiver</code> on the parent, and
		 * expands the receiver.
		 */
		protected void expandParentAndReceiver() {
			PhylTreeStateNode parent = (PhylTreeStateNode) getParent();

			if (parent != null) {
				parent.expandParentAndReceiver();
			}
			expand();
		}

		/**
		 * Expands this node in the tree. This will load the children from the
		 * treeModel if this node has not previously been expanded. If
		 * <I>adjustTree</I> is true the tree and selection are updated
		 * accordingly.
		 */
		@SuppressWarnings("unchecked")
		protected void expand() {
			int originalRow = getRow();

			updatePreferredSize(originalRow);

			if (!hasBeenExpanded) {
				PhylTreeStateNode newNode;
				Object realNode = getValue();
				TreeModel treeModel = getModel();
				int count = treeModel.getChildCount(realNode);

				hasBeenExpanded = true;
				if (originalRow == -1) {
					for (int i = 0; i < count; i++) {
						newNode = createNodeForValue(treeModel.getChild(
								realNode, i));
						this.add(newNode);
						newNode.updatePreferredSize(-1);
					}
				} else {
					int offset = originalRow + 1;
					for (int i = 0; i < count; i++) {
						newNode = createNodeForValue(treeModel.getChild(
								realNode, i));
						this.add(newNode);
						newNode.updatePreferredSize(offset);
					}
				}

				int i = originalRow;
				Enumeration cursor = preorderEnumeration();
				cursor.nextElement(); // don't add me, I'm already in

				int newYOrigin;

				newYOrigin = getYOrigin() + this.getPreferredHeight();
				PhylTreeStateNode aNode;
				while (cursor.hasMoreElements()) {
					aNode = (PhylTreeStateNode) cursor.nextElement();
					if (!updateNodeSizes && !aNode.hasValidSize()) {
						aNode.updatePreferredSize(i + 1);
					}
					aNode.setYOrigin(newYOrigin);
					newYOrigin += aNode.getPreferredHeight();
					visibleNodes.insertElementAt(aNode, ++i);
				}

				// Update the rows in the selection
				if (treeSelectionModel != null) {
					treeSelectionModel.resetRowSelection();
				}
			}
		}

		/**
		 * Removes the receiver, and all its children, from the mapping table.
		 */
		protected void removeFromMapping() {
			if (path != null) {
				removeMapping(this);
				for (int counter = getChildCount() - 1; counter >= 0; counter--) {
					((PhylTreeStateNode) getChildAt(counter))
							.removeFromMapping();
				}
			}
		}
	} // End of VariableHeightLayoutCache.TreeStateNode

	/**
	 * An enumerator to iterate through visible nodes.
	 */
	private class PhylTreeStateNodeEnumeration implements Enumeration<TreePath> {

		/** Parent thats children are being enumerated. */
		protected PhylTreeStateNode parent;

		/**
		 * Index of next child. An index of -1 signifies parent should be
		 * visibled next.
		 */
		protected int nextIndex;

		/** Number of children in parent. */
		protected int childCount;

		protected PhylTreeStateNodeEnumeration(PhylTreeStateNode node) {
			this(node, -1);
		}

		protected PhylTreeStateNodeEnumeration(PhylTreeStateNode parent,
				int startIndex) {
			this.parent = parent;
			this.nextIndex = startIndex;
			this.childCount = this.parent.getChildCount();
		}

		/**
		 * @return true if more visible nodes.
		 */
		public boolean hasMoreElements() {
			return (parent != null);
		}

		/**
		 * @return next visible TreePath.
		 */
		public TreePath nextElement() {
			if (!hasMoreElements()) {
				throw new NoSuchElementException("No more visible paths");
			}

			TreePath retObject;

			if (nextIndex == -1) {
				retObject = parent.getTreePath();
			} else {
				PhylTreeStateNode node = (PhylTreeStateNode) parent
						.getChildAt(nextIndex);

				retObject = node.getTreePath();
			}
			updateNextObject();
			return retObject;
		}

		/**
		 * Determines the next object by invoking <code>updateNextIndex</code>
		 * and if not succesful <code>findNextValidParent</code>.
		 */
		protected void updateNextObject() {
			if (!updateNextIndex()) {
				findNextValidParent();
			}
		}

		/**
		 * Finds the next valid parent, this should be called when nextIndex is
		 * beyond the number of children of the current parent.
		 */
		protected boolean findNextValidParent() {
			if (parent == root) {
				// mark as invalid!
				parent = null;
				return false;
			}
			while (parent != null) {
				PhylTreeStateNode newParent = (PhylTreeStateNode) parent
						.getParent();

				if (newParent != null) {
					nextIndex = newParent.getIndex(parent);
					parent = newParent;
					childCount = parent.getChildCount();
					if (updateNextIndex()) {
						return true;
					}
				} else {
					parent = null;
				}
			}
			return false;
		}

		/**
		 * Updates <code>nextIndex</code> returning false if it is beyond the
		 * number of children of parent.
		 */
		protected boolean updateNextIndex() {

			// Check that it can have kids
			if (childCount == 0) {
				return false;
			} else if (++nextIndex >= childCount) {
				return false;
			}

			PhylTreeStateNode child = (PhylTreeStateNode) parent
					.getChildAt(nextIndex);

			if (child != null) {
				parent = child;
				nextIndex = -1;
				childCount = child.getChildCount();
			}
			return true;
		}
	} // VariableHeightLayoutCache.VisibleTreeStateNodeEnumeration

}
